package cuiyt.algorithm.dfs;

import algorithm.TreeNode;

/**
 * @author cyt
 * @create 2020-09-04 9:13
 */
public class T106 {
    public static void main(String[] args) {

    }

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int postLen = postorder.length;
        int inLen = inorder.length;
        return new TreeNode();
    }

    /**
     * 中序遍历 inorder = [9,3,15,20,7]
     * 后序遍历 postorder = [9,15,7,20,3]
     * <p>
     * 返回如下的二叉树：
     * <p>
     * 3
     * / \
     * 9  20
     * /  \
     * 15   7
     * 3  9 15 20 7
     * 9 15 7 20 3
     **/

    public TreeNode dfs(int[] inorder, int[] postorder, int l, int r) {
        TreeNode node = new TreeNode();
        node.val = postorder[r - 1];
        /**
         * 找到先序遍历中的根节点位置
         */
        int left;
        for (left = 0; left < r; left++) {
            if (inorder[left] == node.val) {
                break;
            }
        }

        int right = r - 1 - left;

        node.left = dfs(inorder, postorder, left, left);
        node.right = dfs(inorder, postorder, right, right);
        return node;
    }
}
